/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) 
    {
        //处理边界情况
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr) 
            return;
        //1、找链表中间节点
        ListNode *fast = head, *slow = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        //2、逆置部分链表
        ListNode* head2 = new ListNode;
        ListNode* cur = slow->next;
        slow->next = nullptr;//断开链表

        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = head2->next;
            head2->next = cur;
            cur = next;
        }

        //合并两个链表
        ListNode* ret = new ListNode;
        ListNode* prev = ret;
        ListNode* cur1 = head, *cur2 = head2->next;
        while(cur1)
        {
            prev->next = cur1;
            cur1 = cur1->next;
            prev = prev->next;
            if(cur2)
            {
                prev->next = cur2;
                prev = prev->next;
                cur2 = cur2->next;
            }
        }
        delete ret;
        delete head2;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        return merge(lists, 0, lists.size()-1);
    }
    ListNode* merge(vector<ListNode*>& lists, int left, int right)
    {
        //处理递归条件
        if(left > right) return nullptr;
        if(left == right) return lists[left];

        int mid = (left + right) >> 1;
        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid+1, right);

        return mergeTwoList(l1, l2);
    }
    ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
    {
        //处理边界情况
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;

        //归并排序思想进行合并
        ListNode* guard = new ListNode;
        ListNode* cur1 = l1, *cur2 = l2, *prev = guard;
        while(cur1 && cur2)
        {
            if(cur1->val <= cur2->val)
            {
                prev->next =cur1;
                prev = cur1;
                cur1 = cur1->next;
            }
            else
            {
                prev->next =cur2;
                prev = cur2;
                cur2 = cur2->next;                
            }
        }

        if(cur1) prev->next = cur1;
        if(cur2) prev->next = cur2;

        prev = guard->next;
        delete guard;
        return prev;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        int len = 0;
        ListNode* cur = head;
        while(cur)
        {
            ++len;
            cur = cur->next;
        }
        int n = len / k; // 一共分成多少组
        cur = head;
        ListNode* guard = new ListNode;
        ListNode* prev = guard;
        ListNode* tmp;

        for(int i = 0; i < n; i++)
        {
            tmp = cur;
            for(int j = 0; j < k; j++)
            {
                ListNode* next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev->next = cur;
        cur = guard->next;
        delete guard;
        return cur;
    }
};
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        unordered_map<int,int> hash;
        for(int i = 0; i < nums.size(); i++)
        {
            int x = target - nums[i];
            if(hash.count(x)) return {hash[x], i};
            hash.insert({nums[i],i});
        }   
        return {0,1};
    }
};

class Solution {
public:
    bool CheckPermutation(string s1, string s2) 
    {
        if(s1.size()!=s2.size()) return false;
        int hash[26] = {0};
        for(auto e : s1)
            hash[e -'a']++;
        for(auto e : s2)
        {
            if(hash[e - 'a'] == 0)
                return false;
            else 
                hash[e - 'a']--;
        }
        return true;
    }
};
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) 
    {
        unordered_set<int> hash;
        for(auto e : nums)
        {
            if(hash.count(e))
                return true;
            else
                hash.insert(e);
        }
        return false;
    }
};
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i++)
        {
            if(hash.count(nums[i]))
            {
                if(i - hash[nums[i]] <= k)
                    return true;
            }
            hash[nums[i]] = i;
        }
        return false;
    }
};
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        //构建hash表，遍历strs元素，并对它们进行排序，然后放入hash表
        unordered_map<string, vector<string>> hash;
        for(auto& s : strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }
        //遍历hash，将配对的结果返回
       vector<vector<string>> ret;
        for(auto &[x,y] : hash)
        {
            ret.push_back(y);
        }
        return ret;
    }   
};

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        string ret = strs[0];
        for(int i = 1; i < strs.size(); i++)
        {
            ret = GetSubstr(ret, strs[i]);
        }
        return ret;
    }
    string GetSubstr(string& s1, string& s2)
    {
        int i = 0;
        while(i < min(s1.size(), s2.size()) && s1[i] == s2[i])
            i++;
        return s1.substr(0, i);
    }
};

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        for(int i = 0; i < strs[0].size(); i++)
        {
            char tmp = strs[0][i];
            for(int j = 1; j < strs.size(); j++)
            {
                if(i == strs[j].size() || strs[j][i] != tmp)
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};
class Solution {
public:
    string longestPalindrome(string s) 
    {
        int begin = 0;
        int maxlen = 0;
        int len = s.size();
        //枚举中心下标
        for(int i = 0; i < len; i++)
        {
            string tmp;
            //奇数情况
            int left = i, right = i;
            while(left >= 0 && right < len && s[left] == s[right])
            {
                left--;
                right++;
            }
            if(right - left - 1 > maxlen)
            {
                begin = left + 1;
                maxlen = right - left - 1;
            }
            //偶数情况
            left = i, right = i+1;
            while(left >= 0 && right < len && s[left] == s[right])
            {
                left--;
                right++;
            }
            if(right - left - 1 > maxlen)
            {
                begin = left + 1;
                maxlen = right - left - 1;
            }
        }
        return s.substr(begin, maxlen);
    }
};
class Solution {
public:
    string addBinary(string a, string b) 
    {
        string ret;
        int cur1 = a.size() - 1,cur2 = b.size() - 1,t = 0;
        while(cur1 >= 0 || cur2 >= 0 || t)
        {
            if(cur1 >= 0) t += a[cur1--] - '0';
            if(cur2 >= 0) t += b[cur2--] - '0';
            ret += t % 2 + '0';
            t /= 2;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

class Solution {
public:
    string multiply(string nums1, string nums2) 
    { 
        string ret;
        int n1 = nums1.size(), n2 = nums2.size();
        vector<int> tmp(n1 + n2 - 1);
        reverse(nums1.begin(), nums1.end());
        reverse(nums2.begin(), nums2.end());


        //将对应位置乘法结果进行累加
        for(int i = 0; i < n1; i++)
        {
            for(int j = 0; j < n2; j++)
            {
                tmp[i + j] += (nums1[i] - '0') * (nums2[j] - '0');
            }
        }

        //处理加法并进位
        int t = 0, cur = 0;
        while(t || cur < n2 + n1 - 1)
        {
            if(cur < n2 + n1 - 1)
                t += tmp[cur++];
            ret += t % 10 + '0';
            t /= 10;
        }

        //处理前导0
        while(ret.size() > 1 && ret.back() == '0') ret.pop_back();

        reverse(ret.begin(), ret.end());

        return ret;
    }
};

class Solution {
public:
    string removeDuplicates(string s) 
    {
        string stack;
        for(int i = 0; i < s.size(); i++)
        {
            if(stack.size() != 0 && s[i] == stack.back())
            {
                stack.pop_back();
            }
            else
            {
                stack += s[i];
            }
        }
        return stack;
    }
};

class Solution {
public:
    bool backspaceCompare(string s, string t) 
    {
        string tmps, tmpt;
        for(auto e : s)
        {
            if(e == '#')
            {
                    if(!tmps.empty())
                tmps.pop_back();
            }
            else
            {
                tmps += e;
            }
        }
        for(auto e : t)
        {
            if(e == '#')
            {
                if(!tmpt.empty())
                    tmpt.pop_back();
            }
            else
            {
                tmpt += e;
            }
        }

        if(tmps.size() != tmpt.size())
            return false;

        
        for(int i = 0; i < tmps.size(); i++)
        {
            if(tmps[i]!= tmpt[i])
                return false;
        }

        return true;
    }
};

class Solution {
public:
    int calculate(string s) 
    {
        vector<int> st; //模拟栈
        char op = '+';
        int i = 0, n = s.size(), ret = 0;
        while(i < n)
        {
            if(s[i] == ' ') 
                i++;
            else if(s[i] >= '0' && s[i] <= '9')
            {
                int tmp = s[i++] - '0';
                while(i < n && s[i] >= '0' && s[i] <= '9') 
                    tmp = tmp * 10 + (s[i++] - '0');
                
                if(op == '+')
                    st.push_back(tmp);
                else if(op == '-')
                    st.push_back(-tmp);
                else if(op == '*')
                    st.back() *= tmp;
                else if(op == '/')
                    st.back() /= tmp;
            }
            else 
            {
                op = s[i++];
            }
        }

        for(auto e : st)
        {
            ret += e;
        }
        
        return ret;
    }
};
class Solution {
public:
    string decodeString(string s) 
    {
        int len = s.size();
        stack<string> str;
        str.push("");
        stack<int> nums;
        int i = 0;
        while(i < len)
        {
            if(s[i] >= '0' && s[i] <= '9')
            {
                int tmp = s[i++] - '0';
                while(s[i] >= '0' && s[i] <= '9')  
                {
                    tmp = tmp * 10 + (s[i++] - '0');
                }
                nums.push(tmp);
            }
            else if(s[i] == '[')
            {
                string tmp = "";
                i++;
                while(s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i++];
                }
                str.push(tmp);
            }
            else if(s[i] == ']')
            {
                string tmp, topStr = str.top();
                str.pop();
                int topNum = nums.top();
                nums.pop();
                for(int i = 0; i < topNum; i++)
                {
                   tmp += topStr;
                }
                topStr = str.top();
                str.pop();
                topStr += tmp;
                str.push(topStr);
                i++;
            }
            else
            {
                string tmp;
                while(s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i++];
                }
                string top = str.top();
                str.pop();
                top += tmp;
                str.push(top);
            }
        }
        return str.top();
    }
};

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        stack<int> st;
        int i = 0, j = 0;
        while(i < pushed.size())
        {
            st.push(pushed[i++]);
            while(!st.empty() && st.top() == popped[j])
            {
                j++;
                st.pop();
            }
        }
        if(st.empty())
            return true;
        else 
            return false;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        vector<vector<int>> ret;
        queue<Node*> q;
        if(root)
            q.push(root);
        else 
            return ret;

        while(!q.empty())
        {
            int n = q.size();
            vector<int> v;
            while(n--)
            {
                Node* cur = q.front();
                v.push_back(cur->val);
                for(auto e : cur->children)
                {
                    q.push(e);
                }
                q.pop();
            }
            ret.push_back(v);
        }
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        vector<vector<int>> ret;
        queue<TreeNode*> q;

        //处理边界情况
        if(root)
            q.push(root);
        else
            return ret;
        
        int flag = 1;
        while(!q.empty())
        {
            vector<int> tmp;
            int n = q.size();
            for(int i = 0; i < n; i++)
            {
                TreeNode* t = q.front();
                tmp.push_back(q.front()->val);
                q.pop();
                if(t->left)
                    q.push(t->left);
                if(t->right)
                    q.push(t->right);
            }
            if(flag++ % 2 != 0)
            {
                ret.push_back(tmp);
            }
            else
            {
                reverse(tmp.begin(), tmp.end());
                ret.push_back(tmp);
            }
        }
        return ret;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) 
    {
        vector<pair<TreeNode*,unsigned int>> q; // 模拟队列
        q.push_back({root, 1});
        unsigned int ret = 0;
        while(q.size())
        {
            //更新结果
            auto& [x1, y1] = q[0];
            auto& [x2, y2] = q.back();
            ret = max(ret, y2 - y1 + 1);
            
            vector<pair<TreeNode*,unsigned int>> tmp; // 保存一层的结果

            for(auto &[x, y] : q)
            {
                if(x->left) tmp.push_back({x->left, y * 2});
                if(x->right) tmp.push_back({x->right, y * 2 + 1});
            }
            q = tmp;
        }
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) 
    {
        queue<TreeNode*> q; 
        vector<int> ret;
        if(root == nullptr) return ret;
        q.push(root);
        while(q.size())
        {
            int sz = q.size();
            int max = INT_MIN; //记录每一层最大值
            for(int i = 0; i < sz; i++)
            {
                TreeNode* f = q.front();
                q.pop();
                if(f->val > max) max = f->val;
                if(f->left) q.push(f->left);
                if(f->right) q.push(f->right);
            }
            ret.push_back(max);
        }
        return ret;
    }
};

class Solution {
public:
    struct cmp
    {
        bool operator()(const pair<string, int>& a, const pair<string, int>& b)
        {
            if(a.second == b.second) //频次相同，按照字典序排序
                return a.first < b.first;
            else //频次不同按照频次比较
                return a.second > b.second;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        
        unordered_map<string, int> hash; // 统计字符串频次
        for(auto& e : words)
            hash[e]++;

        vector<string> ret(k); //用于返回

        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> heap; //创建小根对统计前k个高频词
        for(auto& [x, y] : hash)    
        {
            heap.push({x, y});
            if(heap.size() > k)
            {
                heap.pop();
            }
        }
        
        int n = k - 1;
        while(k--)
        {
            ret[n--] = heap.top().first;
            heap.pop();
        }

        return ret;
    }
};

class Solution {
    //四个方向的坐标向量
    int dx[4] = {0,0,-1,1};
    int dy[4] = {1,-1,0,0};
    int n,m;//统计行列
    bool visi[301][301]; // 题目规定最多只有300

public:
    int numIslands(vector<vector<char>>& grid) 
    {
        n = grid.size(), m = grid[0].size();
        int ret = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(grid[i][j] == '1' && !visi[i][j])
                {
                    bfs(grid,i,j);
                    ret++;
                }
            }
        }    
        return ret;
    }

    void bfs(vector<vector<char>>& grid, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({i,j});

        while(q.size())
        {
            auto [a,b] = q.front();
            q.pop();
            for(int k = 0; k < 4; k++)
            {
                int x = dx[k] + a, y = dy[k] + b;
                if(x >= 0 && x < n && y >=0 && y < m && !visi[x][y] && grid[x][y] == '1')
                {
                    q.push({x, y});
                    visi[x][y] = true;
                }
            }
        }
    }
};

class Solution {
    bool visi[51][51]; // 根据题意可知，最长不超过50
    int n,m;
    //四个方向的坐标向量
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        int ret = 0;
        n = grid.size(), m = grid[0].size();
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(!visi[i][j] && grid[i][j] == 1)
                {
                    ret = max(ret, bfs(grid, i, j));
                }
            }
        }
        return ret;
    }

    int bfs(vector<vector<int>>& grid, int i, int j)
    {
        int ret = 0;
        queue<pair<int, int>> q;
        q.push({i,j});
        visi[i][j] = true;
        while(q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            ret++;
            for(int k = 0; k < 4; k++)
            {
                int x = dx[k] + a, y = dy[k] + b;
                if(x >= 0 && x < n && y >= 0 && y < m && !visi[x][y] && grid[x][y] == 1)
                {
                    q.push({x, y});
                    visi[x][y] = true;
                }
            }
        }
        return ret;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) 
    {
        //出口
        if(q == nullptr && p == nullptr)
            return true;
        //一个结点为空的情况——结构不同
        if(!p || !q)
            return false;
        //值不相等
        if(q->val != p->val)
            return false;

        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        int n = A.size();
        dfs(A, B, C, n);
    }
    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n)
    {
        //递归出口
        if(n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }

        // 1、 将A的n - 1个数，借助C放到B上
        dfs(A, C, B, n - 1);
        //2 、将A[0]，放到C上
        C.push_back(A.back());
        A.pop_back();
        //3、将B剩下的元素借助A放到C上
        dfs(B, A, C, n - 1);
    }
};

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        unordered_set<string> hash(wordList.begin(), wordList.end());
        unordered_set<string> visi; 
        int len = beginWord.size();
        
        //处理边界情况
        if(!hash.count(endWord)) return 0;

        queue<string> q;
        q.push(beginWord);
        visi.insert(beginWord);
        int ret = 1;

        while(q.size())
        {
            int sz = q.size();
            ret++;
            while(sz--)
            {
                string t = q.front();
                q.pop();
                for(int i = 0; i < len; i++)
                {
                    string tmp = t;
                    for(int j = 0; j < 26; j++)
                    {
                        tmp[i] = 'a' + j;
                        if(!visi.count(tmp) && hash.count(tmp))
                        {
                            if(tmp == endWord) return ret;
                            visi.insert(tmp);
                            q.push(tmp);
                        }
                    }
                }
            }
        }

        return 0;
    }
};

class Solution {
    int dx[4] = {0,0,-1,1};
    int dy[4] = {-1,1,0,0};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) 
    {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> dist(n, vector<int>(m, -1));
        queue<pair<int, int>> q;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
            {
                if(mat[i][j] == 0) 
                {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
            }
        
        while(q.size())
        {
            auto [a,b] = q.front();
            q.pop();
            for(int i = 0; i < 4; i++) 
                int x = dx[i] + a, y = dy[i] + b;
                if(x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1)
                {
                    dist[x][y] = dist[a][b] + 1;
                    q.push({x, y});
                }
            }
        }
        return dist;
    }
};